<body></body>

<script type="module">
	import lis from './getSequence.js'
	// 渲染器
	const renderer = createRenderer({
		createElement: (tag) => document.createElement(tag),
		setElementText: (el, text) => (el.textContent = text),
		insert: (el, parent, anchor = null) => parent.insertBefore(el, anchor),
		createText: (text) => document.createTextNode(text),
		createComment: (text) => document.createComment(text),
		setText: (el, text) => (el.nodeValue = text),

		patchProps: (el, key, prevValue, nextValue) => {
			// 特殊处理
			function shouldSetAsProps(el, key, value) {
				if (key === 'form' && el.tagName === 'INPUT') return false
				return key in el
			}
			// 事件处理（带时间戳过滤）
			if (key.startsWith('on')) {
				const invokers = el._vei || (el._vei = {})
				const name = key.slice(2).toLowerCase()

				if (nextValue) {
					if (!invokers[key]) {
						invokers[key] = (e) => {
							if (e.timeStamp < invokers[key].attached) return
							;[].concat(invokers[key].value).forEach((fn) => fn(e))
						}
						invokers[key].value = nextValue
						invokers[key].attached = performance.now()
						el.addEventListener(name, invokers[key])
					} else {
						invokers[key].value = nextValue
					}
				} else if (invokers[key]) {
					el.removeEventListener(name, invokers[key])
				}
			} else if (key === 'class') {
				// el.className = ''
			} else if (shouldSetAsProps(el, key, nextValue)) {
				const type = typeof el[key] //  获取该 DOM 属性值 的类型
				if (type === 'boolean' && nextValue === '') {
					el[key] = true // 如果是dom使用标准是布尔值，并且当前nextValue是空，将值矫正为true
				} else {
					el[key] = nextValue
				}
			} else {
				el.setAttribute(key, nextValue)
			}
		}
	})

	function createRenderer(optios) {
		const { createElement, setElementText, insert, createText, createComment, setText, patchProps } = optios

		// 挂载
		function mountElement(vnode, container, anchor) {
			const el = (vnode.el = createElement(vnode.type))

			// 处理子节点
			if (typeof vnode.children === 'string') {
				setElementText(el, vnode.children)
			} else if (Array.isArray(vnode.children)) {
				vnode.children.forEach((child) => patch(null, child, el))
			}

			// 处理属性
			if (vnode.props) {
				for (const key in vnode.props) {
					patchProps(el, key, null, vnode.props[key])
				}
			}

			insert(el, container, anchor) // 插入容器
		}

		// 卸载
		function unmount(vnode) {
			if (vnode.type === Fragment) {
				vnode.children.forEach(unmount) // 递归卸载片段
			} else {
				const parent = vnode.el.parentNode
				if (parent) parent.removeChild(vnode.el)
			}
		}

		// 渲染函数
		function render(vnode, container) {
			if (vnode) {
				patch(container._vnode, vnode, container) // 新vnode存在，将其与旧vnode一起传递给patch函数打补丁
			} else {
				if (container._vnode) {
					unmount(container._vnode) // newVNode不存在, 且 oldVNode存在 执行卸载(unmount)操作
				}
			}
			container._vnode = vnode // 保存节点
		}

		// 子节点更新：对比 字符串 | 数组 | null
		function patchChildren(oldVNode, newVNode, container) {
			if (typeof newVNode.children === 'string') {
				if (Array.isArray(oldVNode.children)) {
					oldVNode.children.forEach((c) => unmount(c)) // 只有当旧子节点为一组的时候，才需要逐个卸载，其他情况下什么都不需要做
				}
				setElementText(container, newVNode.children) // 最后将新的文本节点内容设置给容器元素
			} else if (Array.isArray(newVNode.children)) {
				if (Array.isArray(oldVNode.children)) {
					patchKeyedChildren(newVNode, oldVNode, container)
				} else {
					setElementText(container, '')
					newVNode.children.forEach((c) => patch(null, c, container))
				}
			} else {
				if (Array.isArray(oldVNode.children)) {
					oldVNode.children.forEach((v) => unmount(v)) // 旧的子节点要么文本子节点，要么不存在，但无论哪种情况，我们都只需要将容器清空，
					// 然后加新的一组字节对数个挂载
				} else if (typeof oldVNode.children === 'string') {
					setElementText(container, '')
				}
			}
		}

		// diff 对比
		function patchKeyedChildren(newVNode, oldVNode, container) {
			const oldChildren = oldVNode.children
			const newChildren = newVNode.children

			// 快速Diff算法
			let j = 0
			let oldStartVNode = oldChildren[j]
			let newStartVNode = newChildren[j]
			// 处理相同的前置, j指向两个Children的开头
			while (oldStartVNode.key === newStartVNode.key) {
				patch(oldStartVNode, newStartVNode, container)
				j++
				oldStartVNode = oldChildren[j]
				newStartVNode = newChildren[j]
			}
			//处理相同的后置
			let oldEndIndex = oldChildren.length - 1
			let newEndIndex = newChildren.length - 1
			let oldEndVNode = oldChildren[oldEndIndex]
			let newEndVNode = newChildren[newEndIndex]
			while (oldEndVNode.key === newEndVNode.key) {
				patch(oldEndVNode, newEndVNode, container)
				oldEndIndex--
				newEndIndex--
				oldEndVNode = oldChildren[oldEndIndex]
				newEndVNode = newChildren[newEndIndex]
			}
			// 处理相同前置和后置之后判断
			if (j <= newEndIndex && j > oldEndIndex) {
				//有相同 newVnode需要挂载，而oldVnode已经全部处理完了
				const anchorIndx = newEndIndex + 1,
					anchor = anchorIndx < newChildren.length ? newChildren[anchorIndx].el : null //如果超出了newChildren.length 那就挂载在后面
				while (j <= newEndIndex) {
					patch(null, newChildren[j++], container, anchor)
				}
			} else if (j > newEndIndex && j <= oldEndIndex) {
				// oldVnode需要卸载，newVnode已经全部处理完了
				while (j <= oldEndIndex) unmount(oldChildren[j++])
			} else {
				const count = newEndIndex - j + 1 //新的一组子节点中剩余未处理节点的数量
				const source = new Array(count).fill(-1) //新的节点在旧的节点的位置

				const oldStart = j
				const newStart = j
				let moved = false //是否需要移动
				let pos = 0 //在旧的节点里面最大索引

				const keyIndex = {}
				for (let i = newStart; i <= newEndIndex; i++) {
					keyIndex[newChildren[i].key] = i
				}

				let patched = 0 //patched 变量，代表更新过的节点数量

				for (let i = oldStart; i <= oldEndIndex; i++) {
					const oldVNode = oldChildren[i]
					// 假如更新过的节点数量小于需要更新的节点数量，那么就需要执行更新
					if (patched <= count) {
						// 通过索引表快速找到新的一组节点 中 具有相同key值节点位置
						const k = keyIndex[oldVNode.key]

						if (typeof k !== 'undefined') {
							newVNode = newChildren[k]
							patched++ //每更新一个节点，都将 patched 变量 +1
							patch(oldVNode, newVNode, container)
							source[k - newStart] = i
							if (k < pos) {
								// 判断节点是否需要移动
								moved = true
							} else {
								pos = k
							}
						} else {
							unmount(oldVNode)
						}
					} else {
						// 如果更新过的节点数量大于需要更新的节点数量，卸载多余的节点
						unmount(oldVNode)
					}
				}

				//如果 moved 为真，则需要进行 DOM 移动操作
				if (moved) {
					const seq = lis(source) // 计算最长递增子序列
					let i = count - 1 //i指向新的一组子节点的最后一个元素
					let s = seq.length - 1 // s指向最长递增子序列的最后一个元素

					for (i; i >= 0; i--) {
						if (source[i] == -1) {
							// 新节点挂载
							const pos = i + newStart
							const newVNode = newChildren[pos] // 该节点的下一个节点的位置索引
							const nextPos = pos + 1
							const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null // 锚点
							patch(null, newVNode, container, anchor)
						} else if (i !== seq[i]) {
							// 说明该节点需要移动
							// 该节点在新的一组子节点的真实位置
							for (i; i >= 0; i--) {
								const pos = i + newStart
								const newVNode = newChildren[pos] // 该节点的下一个节点的位置索引
								const nextPos = pos + 1
								const anchor = nextPos < newChildren.length ? newChildren[nextPos].el : null // 锚点
								insert(newVNode.el, container, anchor) // 移动
							}
						} else {
							// i===seq[i]时，说明该位置的节点不需要移动，s指向下一个位置
							s--
						}
					}
				}
			}
		}
		// 元素差异对比
		function patchElement(oldVNode, newVNode) {
			const el = (newVNode.el = oldVNode.el)
			const oldProps = oldVNode.props || {}
			const newProps = newVNode.props || {}

			// 更新属性 || 新增属性
			for (const key in newProps) {
				if (newProps[key] !== oldProps[key]) {
					patchProps(el, key, oldProps[key], newProps[key])
				}
			}
			for (const key in oldProps) {
				if (!key in newProps) {
					patchProps(el, key, oldProps[key], null)
				}
			}
			// 更新children
			patchChildren(oldVNode, newVNode, el)
		}

		// 补丁函数
		// anchor 描点元素
		function patch(oldVNode, newVNode, container, anchor) {
			// 新旧两者类型不同
			if ((oldVNode && oldVNode.type !== newVNode.type) || !newVNode) {
				unmount(oldVNode)
				oldVNode = null
			}
			// 以下代码： oldVNodeType === newVNodeType
			const type = newVNode.type
			if (typeof type === 'string') {
				if (!oldVNode) {
					mountElement(newVNode, container, anchor)
				} else {
					patchElement(oldVNode, newVNode)
				}
			} else if (type === Text) {
				if (!oldVNode) {
					const el = (newVNode.el = createText(newVNode.children))
					insert(el, container)
				} else {
					const el = (newVNode.el = oldVNode.el)
					if (newVNode.children !== oldVNode.children) {
						setText(el, newVNode.children)
					}
				}
			} else if (type === Comment) {
				if (!oldVNode) {
					const el = (newVNode.el = createComment(newVNode.children))
					insert(el, container)
				} else {
					const el = (newVNode.el = oldVNode.el)
					if (newVNode.children !== oldVNode.children) {
						setText(el, newVNode.children)
					}
				}
			} else if (type === Fragment) {
				if (!oldVNode) {
					newVNode.children.forEach((v) => patch(null, v, container))
				} else {
					patchChildren(oldVNode, newVNode, container)
				}
			} else if (typeof type === 'object') {
				// 组件类型的Vnode
			} else if (type === 'xxx') {
				// 其他类型的Vnode
			}
		}

		return { render }
	}

	const Fragment = Symbol()
	const Text = Symbol()

	const oldVNode = {
		type: 'div',
		children: [
			{ type: 'p', children: 'p1', key: 1 },
			{ type: 'p', children: 'p2', key: 2 },
			{ type: 'p', children: 'p3', key: 3 },
			{ type: 'p', children: 'p4', key: 4 },
			{ type: 'p', children: 'p6', key: 6 },
			{ type: 'p', children: 'p5', key: 5 }
		]
	}

	let newVNode = {
		type: 'div',
		children: [
			{ type: 'p', children: 'p1', key: 1 },
			{ type: 'p', children: 'p3', key: 3 },
			{ type: 'p', children: 'p4', key: 4 },
			{ type: 'p', children: 'p2', key: 2 },
			{ type: 'p', children: 'p7', key: 7 },
			{ type: 'p', children: 'p5', key: 5 }
		]
	}
	renderer.render(oldVNode, document.body)
	// 新增节点
	setTimeout(() => renderer.render(newVNode, document.body), 1000)
	/*
口 判断是否需要进行 DOM 移动操作。 moved 作为标识，当它的值为 true时，说明需要进行 DOM 移动操作。
口构建 source 数组。该数组的长度等于新的一组子节点去掉相同的前置/后置节点后，剩余未处理节点的数量。
source 数组中存储着新的一组子节点中的节点在旧的一组子节点中的位置，后面根据 source 数组计算出一个最长递增子序列，用于 DOM 移动操作。
	*/
</script>
